# LeetCode 496.下一个更大元素
# https://leetcode.cn/problems/next-greater-element-i/

from typing import List


class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        stack = []
        more = {}
        for index, num in enumerate(nums2):
            if index == 0:
                stack.append(num)
                continue

            while num > stack[-1]:
                pop_num = stack.pop(-1)
                more[pop_num] = num
                if not stack:
                    break
            stack.append(num)

        for num in stack:
            more[num] = -1

        result = []
        for num in nums1:
            result.append(more[num])

        return result


if __name__ == '__main__':
    nums1 = [2, 4]
    nums2 = [1, 2, 3, 4]
    result = Solution().nextGreaterElement(nums1, nums2)
    print(result)
